/*
 * @lc app=leetcode.cn id=64 lang=golang
 *
 * [64] 最小路径和
 */

// 2. 动态规划
// @lc code=start
func minPathSum(grid [][]int) int {
	dp := make(map[string]int) // key: i-j
	dp["0-0"] = grid[0][0]
	for i := 1; i < len(grid); i++ {
		dp[getKey(i, 0)] = dp[getKey(i-1, 0)] + grid[i][0]
	}

	for i := 1; i < len(grid[0]); i++ {
		dp[getKey(0, i)] = dp[getKey(0, i-1)] + grid[0][i]
	}

	for i := 1; i < len(grid); i++ {
		for j := 1; j < len(grid[i]); j++ {
			dp[getKey(i, j)] = min(dp[getKey(i, j-1)], dp[getKey(i-1, j)]) + grid[i][j]
		}
	}
	return dp[getKey(len(grid)-1, len(grid[0])-1)]
}

func getKey(i, j int) string {
	return strconv.Itoa(i) + "-" + strconv.Itoa(j)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

// 1. 深度优先 超时25/61
// @lc code=start
func minPathSum(grid [][]int) int {
	ans := math.MaxInt64
	var dfs func(i, j, sum int)
	dfs = func(i, j, sum int) {
		if i == len(grid)-1 && j == len(grid[0])-1 {
			ans = min(ans, sum+grid[i][j])
			return
		}

		if i >= len(grid) || j >= len(grid[0]) {
			return
		}

		dfs(i+1, j, sum+grid[i][j])
		dfs(i, j+1, sum+grid[i][j])
	}

	dfs(0, 0, 0)
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

